//
// Created by bleedingfight on 2020/7/7.
//
#include "threeSum.h"
std::vector<std::vector<int>> threeSum(std::vector<int>& nums){
    std::vector<std::vector<int>>result;
    int size = nums.size();
    if(size<3)
        return result;
    std::sort(nums.begin(),nums.end());
    for(int current_index = 0;current_index<size;current_index++){
        if(nums[current_index]>0)
            break;
        if(current_index>0&&nums[current_index]==nums[current_index-1])continue;
        int left_index = current_index+1;
        int right_index = size-1;
        while(left_index<right_index){
            int sum_result = nums[current_index]+nums[left_index]+nums[right_index];
            if(sum_result == 0){
//                result.push_back({current_index,left_index,right_index});
                    result.push_back({nums[current_index],nums[left_index],nums[right_index]});
                while (left_index<right_index&&nums[left_index] == nums[left_index+1])
                    left_index++;
                while (left_index<right_index&&nums[right_index] == nums[right_index-1])
                    right_index--;
                left_index++;
                right_index--;
            }
            if(sum_result<0)
                left_index++;
            else if(sum_result>0)
                right_index--;
        }
    }
    return result;
}
